package Array;
//移除元素
/*
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k
*/
/*输入：nums = [0,1,2,2,3,0,4,2], val = 2
    输出：5, nums = [0,1,4,0,3,_,_,_]
    解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
    注意这五个元素可以任意顺序返回。
    你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。*/
public class remove_element {
    /**
     * 思路过程:双指针(左右/相向指针法)
     * 采用双指针，一个从左开始，一个从右开始，左边遇到为val的则停下，右边遇到非val的则停下，然后进行交换
     */
    public int removeElement(int[] nums, int val) {
    int left=0;
    int right=nums.length-1;
    while (left<=right){
        //交换过程
        if(nums[left]==val&&nums[right]!=val){
            /**
             * 这里改进：这里并不需要去交换，只需要覆盖即可，因为题目没有要求后面的是什么样
             * int a=nums[left];
             * nums[left]=nums[right];
             * nums[right]=a;
             */
            nums[left]=nums[right];
            //注意这里交换后 指针要移动
            left++;
            right--;
            continue;
        }
        // 如果不符合再去移动
        if(nums[left]!=val){
            left++;
        }
        if(nums[right]==val){
            right--;
        }
    }
    //返回的就是剩余元素的数量
    return left;
    }
    /**
     * 快慢指针做法
     * 思路：定义两个指针，快指针指向新数组所需要的元素【！=val的】，慢指针指向所要更新的位置[即值=val的】，因为要被替换，所以去找=val的位置，即要更新的位置
     *
     */
    public int removeElement_slow(int[] nums, int val) {
        int slow=0;
        int fast=0;
        while (fast<nums.length){
            //nums = [0,1,2,2,3,0,4,2], val = 2
            /**
             * 演变过程
             * 1.索引为0、1时，这两个操作的快慢指针的位置都是一样的
             * 2.当fast和slow都到索引为2时，发生了变化，因为val=2时，nums[fast]==val，所以此时slow不++，而fast++
             * 3.即slow指向的位置2，应该是得被替换的，然后fast继续移动
             * 4.移动到位置4时，nums[fast]!=val 执行覆盖操作，把索引为2的2覆盖为3，这样子就实现了原数组的改变，原数组的删除操作
             */
            if(nums[fast]!=val){
                nums[slow]=nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}
